#leetcode题目347：前k个高频元素
#难度：中等
#时间复杂度：O(nlogk)
#空间复杂度：O(n)
#方法：堆

import heapq
from typing import List
class Solution:
    # def topKFrequent(self, nums: List[int], k: int) -> List[int]:
    #     """
    #     前k个高频元素
    #     给定一个整数数组 nums 和一个整数 k，请返回数组中出现频率前 k 高的元素。
    #     你可以按任意顺序返回答案。
    #     """
    #     freq = {}
    #     for num in nums:
    #         freq[num] = freq.get(num, 0) + 1
    #     return heapq.nlargest(k, freq.keys(), key=freq.get)
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        """
            前k个高频元素
            给定一个整数数组 nums 和一个整数 k，请返回数组中出现频率前 k 高的元素。
            你可以按任意顺序返回答案。
        """
        # 统计频率
        freq_map = {}
        for num in nums:
            freq_map[num] = freq_map.get(num, 0) + 1
        
        # 使用最小堆维护前k个高频元素
        # 堆中存储 [频率, 数字] 的元组
        heap = []
        
        for num, freq in freq_map.items():
            # 将 [频率, 数字] 加入堆
            heapq.heappush(heap, (freq, num))
            
            # 如果堆的大小超过k，移除频率最小的元素
            if len(heap) > k:
                heapq.heappop(heap)
        
        # 提取结果
        result = []
        while heap:
            result.append(heapq.heappop(heap)[1])
        
        return result



#测试数据
nums = [1,1,1,2,2,3]
k = 2
#预期输出：[1,2]
solution = Solution()
print(solution.topKFrequent(nums, k))

nums = [1]
k = 1
#预期输出：[1]
solution = Solution()
print(solution.topKFrequent(nums, k))